#include "LinkList.h"
//初始化 - 构造一个空的线性表L
LinkList InitList(void)
{
	LinkList L = NULL;
	L = (LinkList)malloc(sizeof(LNode));
	if (!L->data)
	{
		printf("内存分配失败!\n");
		exit(OVERFLOW);
	}
	L->next = NULL;
    return L;
}

//创建单链表
void CreateList_H(LinkList L)//头插法(前插法)创建单链表
//创建一个只有头节点的空链表,根据待创建链表包括的元素个数n，循环n次执行:
//生成新的节点*pNew,输入元素值赋给新节点*pNew的数据域,将新节点*pNew插入到头结点之后
{
	int i = 0;
	int len = 0;//添加元素的总个数
	ElemType e = 0;
	ElemType val = 0;//存放临时变量
	LinkList pNew = NULL;

	printf("请输入要添加的元素的个数:>");
	scanf("%d", &len);
	getchar();
	for (i = len; i > 0; i--)
	{
		printf("第%d个节点为:>", i);
		scanf("%c", &val);
		getchar();
		pNew = (LinkList)malloc(sizeof(LNode));
		pNew->data = val;
		pNew->next = L->next;
		L->next = pNew;
	}
}

void CreateList_R(LinkList L)//尾插法(后插法)创建单链表
//创建一个只有头节点的空链表,尾指针r初始化，指向头节点,根据创建链表包括的元素个数n，循环n次执行:
//生成新节点*p,输入元素值赋给新节点*p的数据域,将新节点*p插入尾节点*r之后,尾指针r指向新的尾节点*p
{
	int i = 0;
	int len = 0;//添加元素的总个数
	ElemType val = 0;//存放临时变量
	LinkList r = NULL, p = NULL;
	r = (LinkList)malloc(sizeof(LNode));
	r = L;

	printf("请输入要添加的元素的个数:>");
	scanf("%d", &len);
	getchar();
	for (i; i < len; i++)
	{
		printf("第%d个元素为:>", i + 1);
		scanf("%c", &val);
		getchar();
		p = (LinkList)malloc(sizeof(LNode));
		p->data = val;
		r->next = p;
		r = p;
		r->next = NULL;
	}
}

//销毁
void DestroyList(LinkList L)
{
	//参考“《数据结构》算法实现及解析”
	LinkList p = NULL;
	while (L)
	{
		p = L->next;
		free(L);
		L = p;
	}
	////以下为自己思考编写的实现代码
	//LinkList p = L;
	////先置空L中所有的元素,然后释放头结点
	//ClearList(p);
	//free(L);
}

//置空
void ClearList(LinkList L)
{
	LinkList p1 = NULL, p2 = NULL;
	while (L->next != NULL)
	{
		p1 = L, p2 = L->next;
		while (p2->next != NULL)
		{
			p1 = p1->next;
			p2 = p2->next;
		}
		free(p2);
		p1->next = NULL;
	}
}

//判空(若线性表L为空表,则返回TRUE，否则返回FALSE)
Status ListEmpty(LinkList L)
{
	if (NULL == L->next)
	{
		printf("单链表为空!\n");
	}
	else
	{
		printf("单链表不为空\n");
	}
}

//返回L中数据元素的个数
Status ListLength(const LinkList L)
{
	int len = 0;//记录链表元素的个数
	LinkList p = L->next;
	while (p != NULL)
	{
		p = p->next;
		len++;
	}
	return len;
}

//用e返回L中第i个数据元素的值.(初始条件:线性表已存在,且1 ≤ i ≤ ListLength(L))
ElemType GetElem(const LinkList L, int x, ElemType e)
{
	int i = 1, len = 0;
	LinkList p = L;
	len = ListLength(p);
	p = L->next;
  
	if (x < 1 || x> len)
	{
		return ERROR;
	}
	while (i != x)
	{
		p = p->next;
		i++;
	}
	e = p->data;
	return e;
}

//返回L中第1个与e相同的允许在L中的位置。若这样的元素不存在，则返回值为0
Status LocateElem(LinkList L, ElemType e)
{
	int i = 0;
	LinkList p = L;
	while (p != NULL && e != p->data  )
	{
		p = p->next;
		i++;
		if (p!=NULL && e == p->data)
		{
			return i;
		}
	}
	return 0;
}

//若cur_e是L的数据元素,且不是第一个，则用pre_e返回其前驱,否则操作失败,pre_e无定义
ElemType PriorElem(const LinkList L, ElemType cur_e, ElemType* p_pre_e)
{
	int i = 0;
	LinkList p = L->next;
	if (cur_e == p->data)
	{
		return ERROR;
	}
	*p_pre_e = p->data;
	p = p->next;
	for (i;p != NULL; p = p->next)
	{
		if (cur_e == p->data)
		{
			return *p_pre_e;
		}
		*p_pre_e = p->data;
	}
	return ERROR;
}

//若cur_e是L的数据元素，且不是最后一个，则用next_e返回其后继，否则操作失败，next_e无定义
ElemType NextElem(const LinkList L, ElemType cur_e, ElemType* p_next_e)
{
	int i = 0;
	LinkList p = L->next;
	LinkList n = p->next;
	for (i; p!=NULL; i++)
	{
		if (p->next != NULL && cur_e == p->data)
		{
			p_next_e = p->next;
			return *p_next_e;
		}
		if (NULL == n)   //此处是为检测p此时为链表的最后一个元素
		{
			return ERROR;
		}
		p = p->next;
		n = p->next;
	}
	return ERROR;
}

//在L中第i个位置之前插入新的数据元素e，L的长度+1
void ListInsert(LinkList L, int x, ElemType e)
{
	int i = 0;
	LinkList p1 = L;
	LinkList p2 = L->next;
	LinkList pNew = NULL;
	for (i = 0; i != x - 1; i++)
	{
		p1 = p1->next;
		p2 = p2->next;
	}
	pNew = (LinkList)malloc(sizeof(LNode));
	pNew->data = e;
	p1->next = pNew, pNew->next = p2;
}

//删除L的第i个元素，L的长度-1
void ListDelete(LinkList L, int x)
{
	int i = 0;
	LinkList p1 = L;
	LinkList p2 = L->next->next;
	LinkList p = NULL;   //用于指向要删除的节点
	for (i = 0; i != x - 1; i++)
	{
		p1 = p1->next;
		p2 = p2->next;
	}
	p = p1->next;
	p->next = NULL;
	p1->next = p2;
	free(p);
}

//对线性表L进行遍历，在遍历过程中对L的每个结点访问一次
void TraverseList(const LinkList L)
{
	LinkList p = L->next;
	printf("遍历:>");
	while (NULL != p)
	{
		printf("%c ", p->data);
		p = p->next;
 	}
	printf("\n");
}

//排序(升序)
void SortList(LinkList L)
{
	LinkList p1 = NULL,   //指向调整位的前一个节点
		p = NULL,    //指向需要移动的节点位
		p2 = NULL,   //指向调整位的后一个节点,并在需要调整位置时指向调整位
		p_Tail = NULL;   //尾指针,始终指向循环遍历时相对的最后一个元素
	
	while (p_Tail != L->next)
	{
		p1 = L, p = L->next, p2 = L->next->next;
		while (p->next != NULL && p->next != p_Tail)
		{
			if (p2 != NULL && p->data > p2->data)
			{
				p = p2;
				p2 = p1->next;
				p1->next = p;
				p2->next = p->next;
				p->next = p2;
			}
			p1 = p1->next;
			p = p->next;
			p2 = p2->next;
		}
		p_Tail = p;
	}
}